Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

题目大意:删除给定链表中所有重复过的元素,只留下没有重复过的元素,例如 1->2-2,返回 1

题目难度:Medium

/**
 * Created by gzdaijie on 16/5/11
 * 思路:A->B->C->D,A为确认不重复的节点,value = B.value,比较C及之后节点val == value ?
 * 相等则移除,若不相等,更新 A,以及value
 * 空间复杂度 O(1)
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode h = new ListNode(0);
        ListNode p;
        h.next = head;
        head = h;

        while (h != null && h.next != null) {
            int value = h.next.val;
            int count = 1;
            p = h.next.next;

            while (p!= null && p.val == value) {
                p = p.next;
                ++count;
            }
            if (count > 1) {
                h.next = p;
            } else {
                h = h.next;
            }
        }
        return head.next;
    }
}
gzdaijie            updated 2016-05-11 20:32:41

results matching ""

    No results matching ""